package com.dyz.leetcode;

import java.util.Arrays;

public class LongestPalindrome5 {
    public static void main(String[] args) {
        String a = new LongestPalindrome5().longestPalindrome("aaaaa");
        System.out.println(a);
    }
    public String longestPalindrome(String s) {
        int len =s.length();
        if(len==0||len==1){return s;}
        //定义二维数组存储值，dp值为1表示true,为0表示false
        int[][] dp = new int[len][len];
        int start = 0;  //回文串的开始位置
        int max = 1;   //回文串的最大长度

        //len=1
        //对角线自己和自己就是回文字符串
        for(int i=0; i<len; i++){
            dp[i][i] = 1;
        }

        //len=2
        //左右两边相等
        for (int i=0; i<len-1; i++){
            if(s.charAt(i)==s.charAt(i+1)){
                dp[i][i+1]=1;
                start=i;
                max = 2;
            }
        }

        //len==3 //j表示检索的子串长度，等于3表示先检索长度为3的子串，就是窗口大小为3的时候
        for(int j=3;j<=len;j++) {
            for (int i = 0; i + j -1<len; i++) {
                int e = j + i - 1;  //终止字符位置
                char front = s.charAt(i);
                char end = s.charAt(e);
                //dp[i][j] = dp[i+1][j-1] and S_i = s_j
                if (front == end && dp[i + 1][e - 1] == 1) {
                    dp[i][e] = 1;
                    //开始位置
                    start = i;
                    //最大长度
                    max = j;
                }
            }
        }
        return s.substring(start,start + max);
    }

    //中心扩散法则
    public String longestPalindrome1(String s) {

        if(s==null||s.length()==0){
            return "";
        }

        int start =0;
        int end =0;
        for (int i=0; i<s.length(); i++){
            int len1 = expandAroundCenter(s, i, i);//奇数的时候
            int len2 = expandAroundCenter(s, i, i+1);//偶数的时候

            int len = Math.max(len1, len2);
            if (len> end-start){
                start = i - (len-1)/2;
                end = i+ len/2;
            }
        }
        return s.substring(start, end+1);
    }
    private int expandAroundCenter(String s, int left, int right){
        int L= left;
        int R = right;
        while(L>=0 && R<s.length()&&s.charAt(L)==s.charAt(R)){
            L--;
            R++;
        }
        return R-L-1;
    }
}
